#include "binHeapMin.h"

// Constroi heap vazio
binHeapMin::binHeapMin(int tamanho)
  : tam(tamanho), vetor(new arvbin*[tamanho+1]()), n(0) 
{
	
}
// Destrutor
binHeapMin::~binHeapMin()
{
  //delete [] vetor;
}
  
//Constroi heap
void binHeapMin::constroiHeap( )
{
	for( int i = n / 2; i > 0; i-- )
	{
        refaz( i , n);
	}
	imprime();
}

//Refaz condicao do heap
void binHeapMin::refaz( int esq, int dir )
{
	int filho;
    arvbin x = *vetor[ esq ];

    for( ; esq * 2 <= dir; esq = filho )
    {
        filho = esq * 2;
		if( filho != dir && vetor[ filho + 1 ]->val.frequencia < vetor[ filho ]->val.frequencia)
            filho++;
        if( vetor[ filho ]->val.frequencia < x.val.frequencia )
            vetor[ esq ] = vetor[ filho ];
        else
            break;
    }
    *vetor[ esq ] = x;

}
// Le dados via teclado e inesqre no heap
void binHeapMin::carregaDados()
{
    no val;

    for(int i = 1; i < tam+1; i++)
	{
		cout << "Digite o simbolo e a frequencia" << endl;
		cin >> val.simbolo;
		cin >> val.frequencia;

		arvbin *x = new arvbin(val);
		insere(x);
	}
	
}

// Inesqre x no heap
void binHeapMin::insere(arvbin* &x) 
{
	int dir;
  
	if ( tam == n )
	{
		cout << "Fila de prioridades cheia!\n";
		return;
	}
  
	/* inicializa esqntinela */  
	vetor[ 0 ] = x;  
	n++;
	dir = n;
  
	/* Refaz heap (sobe elemento) */
	for( ; x->val.frequencia < vetor[dir/2]->val.frequencia; dir /= 2 )
		vetor[dir] = vetor[ dir/2 ];
	
	vetor[dir] = x;
} 

// Executa o procedimento Huffman
void binHeapMin::Huffman()
{
	arvbin *esq;
	arvbin *dir;
    no x;
    while (n>1)
    {
        removeMin(esq);
        removeMin(dir);
        x.simbolo = ' ';
        x.frequencia = esq->val.frequencia + dir->val.frequencia;
        arvbin *r = new arvbin(x, esq, dir);
        insere(r);
        imprime();
    }
    cout << endl << "Arvore em pre-ordem" << endl;
    for (int i=1; i<=n; i++)
        vetor[i]->mostra();
    cout << endl; 
}

//Chama a funcao mostra codigo da clasesq arvbin
void binHeapMin::mostraCodigos()
{
    cout << endl << "Codigos de huffman associados aos simbolos";

    arvbin *x;
    removeMin(x);

    int *vet = new int[tam];
    x->mostraCodigo(0,vet,x);
    cout << endl;
}

// Remove e retorna menor item
void binHeapMin::removeMin( arvbin* & itemMin ) // colocar uma arvore no lugar do int
{
    if( vazia( ) ){
     cout << "Fila de prioridades vazia!";
     return;    
    }         
    itemMin = vetor[1];
    vetor[ 1 ] = vetor[ n-- ];
    refaz( 1 , n );
}

//Teste esq heap vazio
bool binHeapMin::vazia( ) const
{
    return n == 0;
}

void binHeapMin::imprime()
{
	cout << endl << "Heap Binario:" << endl;
	for(int i = 1; i<= n; i++)
	{
		cout << "v[" << i << "] = " << vetor[i]->val.simbolo << " " << vetor[i]->val.frequencia <<endl;
	}
	cout << '\n';
}
